/**
 * 该模块实现了一个优先级队列。
 * 更多信息请参考 http://www.cnblogs.com/lucifer1982/archive/2008/06/13/1218559.html
 * License: BSD
 * Authors: Lucifer (786325481@QQ.com)
 * Copyright: Copyright (C) 2008 Lucifer. All rights reserved.
 */

module system.collections.PriorityQueue;

import system.Array;
import system.Traits;
import system.Exception;
import system.collections.IEnumerator;
import system.collections.IEnumerable;
import system.collections.ICollection;
import system.collections.IQueue;
import system.collections.IComparer;
import system.collections.Comparer;

/**
 * 一个基于最小二叉堆的无界优先级队列。
 * Comments:
 * 		优先级队列不允许使用 null 元素。
 */
public class PriorityQueue(T) : IEnumerable!(T), ICollection!(T), IQueue!(T)
{
	private int theSize;
	private int theVersion;
	private T[] theArray;
	private IComparer!(T) theComparer;
	private const int defaultCapacity = 16;

	/**
	 * 使用默认的初始容量（16）创建一个 PriorityQueue，并根据默认比较器对元素进行排序。
	 */
	public this()
	{
		this(defaultCapacity, DefaultComparer!(T).getInstance());
	}

	/**
	 * 使用指定的初始容量创建一个 PriorityQueue，并根据默认比较器对元素进行排序。
	 */
	public this(int initialCapacity)
	{
		this(initialCapacity, DefaultComparer!(T).getInstance());
	}

	/**
	 * 使用默认的初始容量（16）创建一个 PriorityQueue，并根据指定的比较器对元素进行排序。
	 */
	public this(IComparer!(T) comparer)
	{
		this(defaultCapacity, comparer);
	}

	/**
	 * 使用指定的初始容量创建一个 PriorityQueue，并根据指定的比较器对元素进行排序。
	 * Params:
	 * 		initialCapacity = 指定优先级队列初始容量。
	 * 		comparer = 制定比较器。
	 */
	public this(int initialCapacity, IComparer!(T) comparer)
	in
	{
		assert( initialCapacity >= 0 );
	}
	body
	{
		theArray = new T[initialCapacity+1];
		theComparer = comparer;
	}

	/**
	 * 复制指定的集合元素创建一个PriorityQueue，并根据默认比较器对元素进行排序。
	 */
	public this(IEnumerable!(T) collection)
	{
		theComparer = DefaultComparer!(T).getInstance();
		auto currentCollection = cast(ICollection!(T))collection;
		if(currentCollection !is null)
		{
			theSize = currentCollection.count;
			theArray = new T[(theSize+2) * 11 / 10];
			currentCollection.toArray(theArray[1..$]);
		}
		else
		{
			int i = 1;
			foreach(item; collection)
			{
				theArray[i++] = item;
				theSize++;
			}
		}

		this.buildHeap();
	}

	/*
	 * 实现 IEnumerable(T) 接口.
	 */
	public final Enumerator getEnumerator()
	{
		return new Enumerator();
	}

	public int opApply(int delegate (ref T value) dg)
	{
		auto scope enumerator = new Enumerator();
        int result = 0;
		while( enumerator.moveNext() )
		{
			auto value = enumerator.current();
			if( (result = dg(value) ) != 0 )
				break;
		}
		return result;
	}

	/**
     * Throws:
     * 		InvalidOperationException，当在遍历对象时修改了集合。
     */
	public final class Enumerator : IEnumerator!(T)
	{
		/*
		 *  调用 current() 后的数组元素索引。
		 */
		private int cursor;
		private int modCount;

		package this()
		{
			modCount = theVersion;
		}

		public bool moveNext()
		{
			return ++cursor <= theSize;
		}

		public T current()
		{
			if(modCount != theVersion)
				throw new InvalidOperationException("Collection was modified, enumeration operation can not execute.");

			if(cursor <= 0 || cursor > theSize)
				throw new InvalidOperationException("Enumerate failed.");

			return theArray[cursor];
		}

		public void reset()
		{
			if(modCount != theVersion)
				throw new InvalidOperationException("Collection was modified, enumeration operation can not execute.");
			cursor = 0;
			modCount = theVersion;
		}
	}

	/*
	 * 实现 ICollection(T) 接口。
	 */

	/**
	 * 查看优先级队列是否为空。
	 * Returns:
	 *		如果为空，返回 true；否则，返回 false。
	 */
	public final bool isEmpty()
	{
		return theSize == 0;
	}

	/**
	 * 返回优先级队列包含的元素数目。
	 */
	public final int count()
	{
		return theSize;
	}

	/**
	 * 查看优先级队列是否只读。
	 * Returns:
	 *		false。
	 */
	public final bool isReadOnly()
	{
		return false;
	}

	/**
	 * 将指定的元素插入此优先级队列。
	 * Params:
	 *		item = 要添加的元素。
	 * Returns:
	 * 		true。
	 */
	public final bool add(T item)
	{
		return tryAdd(item);
	}

	/// ditto。
	public final bool tryAdd(T item)
	in
	{
		static if( IsReferenceType!(T) )
		{
			assert( item !is null );
		}
	}
	body
	{
		if(theSize+1 == theArray.length)
		{
			int size = theSize == 0 ? defaultCapacity : needGrow();
			theArray.length = size;
		}

		auto hole = ++theSize;

		theArray[0] = item;

		/*
		 * 向上过滤
		 */
		for(; theComparer.compare(item, theArray[hole/2]) < 0; hole /= 2)
		{
			theArray[hole] = theArray[hole/2];
		}

		theArray[hole] = item;

		theVersion++;

		return true;
	}

	///从此优先级队列中移除所有元素。此调用返回后队列为空。
	public final void clear()
	{
		Array.clear!(T)(theArray[0..theSize]);
		theSize = 0;
		theVersion++;
	}

	/**
	 * 从此队列中移除指定元素的单个实例（如果存在）。
	 * Params:
	 *		item = 要从此队列中移除的元素（如果存在）。
	 * Returns:
	 *		如果此队列由于调用而发生更改，则返回 true。
	 */
	public final bool remove(T item)
	{
		auto index = Array.indexOf!(T)(theArray, item);
		if(index != -1)
		{
			removeAt(index);
			return true;
		}

		return false;
	}

	/**
	 * 如果此队列包含指定的元素，则返回 true。
	 * Params:
	 *		要检查是否包含于此队列的对象。
	 */
	public final bool contains(T item)
	{
		return Array.indexOf!(T)(theArray, item) != -1;
	}

	/**
	 * 将优先级队列中的内容拷贝到指定的数组中。
	 */
	public final void toArray(T[] array)
	in
	{
		assert( array !is null );
	}
	body
	{
		Array.copy!(T)(theArray[1..$], array[0..$], theSize);
	}

	/*
	 * 实现 IQueue(T) 接口。
	 */

	///将指定的元素插入此优先级队列。
	public final bool enqueue(T item)
	{
		return tryAdd(item);
	}

	/**
	 * 获取并移除此队列的头。
	 * Throws:
	 * 		InvalidOperationException，当队列为空时。
	 * Comments:
	 *		等效于 remove() 方法。
	 */
	public final T dequeue()
	{
		return remove();
	}

	/**
	 * 获取并移除此队列的头。
	 * Throws:
	 * 		InvalidOperationException，当队列为空时。
	 */
	public final T remove()
	{
		if(isEmpty())
			throw new InvalidOperationException("The queue is empty.");
		auto result = theArray[1];
		theArray[1] = theArray[theSize--];
		percolateDown(1);
		theVersion++;
		return result;
	}

	/**
	 * 获取但不移除此队列的头。
	 * Throws:
	 * 		InvalidOperationException，当队列为空时。
	 */
	public final T peek()
	{
		if(isEmpty())
			throw new InvalidOperationException("The queue is empty.");

		return theArray[1];
	}

	///等效于 tryAdd(T item) 方法。
	public final bool tryEnqueue(T item)
	{
		return tryAdd(item);
	}

	/**
	 * 等效于 peek() 方法，唯一不同的是该方法不抛异常。
	 * Params:
	 * item = 此队列的头。
	 * Returns:
	 * 		如果队列为空，返回 false；否则返回 true。
	 */
	public final bool tryPeek(out T item)
	{
		if(isEmpty())
		{
			item = T.init;
			return false;
		}

		item = theArray[1];
		return true;
	}

	public final bool tryDequeue(out T item)
	{
		if(isEmpty())
		{
			item = T.init;
			return false;
		}

		item = theArray[1];
		theArray[1] = theArray[theSize--];
		percolateDown(1);
		theVersion++;
		return true;
	}

	//构造一个二叉堆
	private void buildHeap()
	{
		for(int i = theSize / 2; i > 0; i--)
		{
			this.percolateDown(i);
		}
	}

	//向下过滤
	private void percolateDown(int hole)
	{
		int child;
		T item = theArray[hole];
		for(; hole * 2 <= theSize; hole = child)
		{
			child = hole * 2;
			//父节点并非总有两个子节点
			if(child != theSize && theComparer.compare(theArray[child+1], theArray[child]) < 0)
			{
				child++;
			}
			if (theComparer.compare(theArray[child], item) < 0)
                   theArray[hole] = theArray[child];
            else
                break;
		}
		theArray[hole] = item;
	}

	//返回内部数组增长后的大小
	private int needGrow()
	{
		int size = theArray.length;
		int newSize = size< 64 ? (size * 2) : (size / 2) * 3;
		assert( newSize >= 0 && newSize <= int.max );
		return newSize;
	}

	private void removeAt(int index)
	in
	{
		assert(index >= 0 && index <= theSize);
	}
	body
	{
		theVersion++;
		auto size = theSize--;
		if( size == index )
		{
			//最后一项元素
			theArray[index] = T.init;
		}
		else
		{
			auto item = theArray[size];
			theArray[size] = T.init;
			theArray[index] = item;
			percolateDown(index);
			if(theComparer.compare(theArray[index], item) == 0)
			{
				theArray[0] = item;
				for(; theComparer.compare(item, theArray[index/2]) < 0; index /= 2)
				{
					theArray[index] = theArray[index/2];
				}

				theArray[index] = item;
			}
		}
	}
}

unittest
{
	class TestPriorityQueue
	{
		void testCtor()
		{
			auto queue = new PriorityQueue!(int)(10);
		}

		void testClear()
		{
			auto queue = new PriorityQueue!(int)(3);
			queue.add(2);
			queue.add(3);
			queue.add(1);

			assert(queue.count == 3);

			queue.clear();

			assert(queue.count == 0);
		}

		void testPQ()
		{
			auto queue = new PriorityQueue!(int)(100);

			queue.add(3);
			queue.add(5);
			queue.add(6);

			queue.remove(5);

			assert(queue.count == 2);

			queue.add(5);
			queue.add(4);

			assert(queue.peek() == 3);

			assert(queue.count == 4);

			queue.add(2);

			queue.remove(3);

			foreach(item; queue)
			{
				//printf("%d",item);
			}
		}
	}

	auto test = new TestPriorityQueue();
	test.testCtor();
	test.testClear();
	test.testPQ();
}